package com.xiaoyg.algorithm;

import java.util.Arrays;

public class MaxProduct {

    public static void main(String[] args) {
        System.out.println(getMaxMin(new int []{1,2,3,4,5,6}));
    }

    public static int sort(int[] nums){
        Arrays.sort(nums);
        int n = nums.length;
        return Math.max(nums[0] * nums[1] * nums[n - 1] , nums[n-1] * nums[n-2] * nums[n-3]);
    }

    //线性扫描
    public static int getMaxMin(int[] nums){
        //最小指默认为最大指
        int min1 = Integer.MAX_VALUE,min2 = Integer.MIN_VALUE;
        //最大值默认最小值
        int max1 = Integer.MIN_VALUE,max2 = Integer.MIN_VALUE,max3 = Integer.MIN_VALUE;

        //时间复杂度为O(n), 循环扫描比较获取最大，最小的三个指的乘积
        for (int x:nums) {
            if (x < min1){
                min2 = min1;
                min1 = x;
            }else if (x < min2){
                min2 = x;
            }
            if (x > max1){
                max3 = max2;
                max2 = max1;
                max1 = x;
            }else if (x > max2){
                max3 = max2;
                max2 = x;
            }else if (x > max3){
                max3 = x;
            }
        }
        return Math.max(min1 * min2 * max1, max1 * max2 * max3);
    }
}
